/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2006-2013. All rights reserved.
 ******************************************************************************************/

#pragma once

#include <iostream>
#include <cstdlib>
#include <stack>
#include <queue>

using namespace std;

#define BinNodePosi(T) BinNode<T>* 
#define stature(p) ((p) ? (p)->height : -1)

#define IsRoot(x) (!((x).parent))
#define IsLChild(x) (!IsRoot(x) && (&(x) == (x).parent->lChild))
#define IsRChild(x) (!IsRoot(x) && (&(x) == (x).parent->rChild))
#define HasParent(x) (!IsRoot(x))
#define HasLChild(x) ((x).lChild)
#define HasRChild(x) ((x).rChild)
#define HasChild(x) (HasLChild(x) || HasRChild(x)) 
#define HasBothChild(x) (HasLChild(x) && HasRChild(x)) 
#define IsLeaf(x) (!HasChild(x))

#define sibling(p) ( \
   IsLChild(*(p)) ? \
      (p)->parent->rChild : \
      (p)->parent->lChild \
) 

#define uncle(x) ( \
   IsLChild(*((x)->parent)) ? \
      (x)->parent->parent->rChild : \
      (x)->parent->parent->lChild \
) 

#define FromParentTo(x) ( \
   IsRoot(x) ? _root : ( \
   IsLChild(x) ? (x).parent->lChild : (x).parent->rChild \
   ) \
)

typedef enum { RB_RED, RB_BLACK} RBColor; 

template <typename T> struct BinNode { 

   T data; 
   BinNodePosi(T) parent; BinNodePosi(T) lChild; BinNodePosi(T) rChild; 
   int height; 
   int npl; 
   RBColor color; 

   BinNode() : parent(NULL), lChild(NULL), rChild(NULL), height(0), npl(1), color(RB_RED) { }
   BinNode(T e, BinNodePosi(T) p = NULL, BinNodePosi(T) lc = NULL, BinNodePosi(T) rc = NULL,
           int h = 0, int l = 1, RBColor c = RB_RED)
      : data(e), parent(p), lChild(lc), rChild(rc), height(h), npl(l), color(c) { }

   int size(); 
   BinNodePosi(T) insertAsLC(T const &); 
   BinNodePosi(T) insertAsRC(T const &); 
   BinNodePosi(T) succ(); 
   template <typename VST> void travLevel(VST&); 
   template <typename VST> void travPre(VST&); 
   template <typename VST> void travIn(VST&); 
   template <typename VST> void travPost(VST&); 

   bool operator<(BinNode const& bn) { return data < bn.data; } 
   bool operator==(BinNode const& bn) { return data == bn.data; } 
/*DSA*/
/*DSA*/BinNodePosi(T) zig(); 
/*DSA*/BinNodePosi(T) zag(); 
};


template <typename T> int BinNode<T>::size() { 
  int s = 1; 
  if (lChild) s += lChild->size(); 
  if (rChild) s += rChild->size(); 
  return s;
}


template <typename T> 
BinNodePosi(T) BinNode<T>::insertAsLC(T const & e) {  return lChild = new BinNode(e, this);  }

template <typename T> 
BinNodePosi(T) BinNode<T>::insertAsRC(T const & e) {  return rChild = new BinNode(e, this);  }


template <typename T> BinNodePosi(T) BinNode<T>::succ() { 
   BinNodePosi(T) s = this; 
   if (rChild) { 
      s = rChild; 
      while (HasLChild(*s)) s = s->lChild; 
   } else { 
      while (IsRChild(*s)) s = s->parent; 
      s = s->parent; 
   }
  return s;
}


template <typename T> template <typename VST>  
void BinNode<T>::travLevel(VST &visit) { 
   queue<BinNodePosi(T)> Q; 
   Q.push(this); 
   while (!Q.empty()) { 
      BinNodePosi(T) x = Q.front();
	  Q.pop();
	  visit(x->data); 
      if (HasLChild(*x)) Q.push(x->lChild); 
      if (HasRChild(*x)) Q.push(x->rChild); 
   }
}


template <typename T> template <typename VST>
void BinNode<T>::travPre(VST& visit) { 
   switch (rand() % 3) { 
      case 1: travPre_I1(this, visit); break; 
      case 2: travPre_I2(this, visit); break; 
      default: travPre_R(this, visit); break; 
   }
}


template <typename T, typename VST> 
void travPre_I1(BinNodePosi(T) x, VST& visit) { 
	stack<BinNodePosi(T)> S; 
	if (x) S.push(x); 
	while (!S.empty()) {
		x = S.top();
		S.pop(); 
		visit(x->data); 
		if (HasRChild(*x)) S.push(x->rChild); if (HasLChild(*x)) S.push(x->lChild); 
   }
}


template <typename T, typename VST> 
static void visitAlongLeftBranch(BinNodePosi(T) x, VST& visit, stack<BinNodePosi(T)>& S) {
   while (x) {
      visit(x->data); 
      S.push(x->rChild); 
      x = x->lChild;  
   }
}

template <typename T, typename VST> 
void travPre_I2(BinNodePosi(T) x, VST& visit) { 
   stack<BinNodePosi(T)> S; 
   while (true) {
      visitAlongLeftBranch(x, visit, S); 
      if (S.empty()) break; 
      x = S.pop(); 
   }
}


template <typename T, typename VST> 
void travPre_R(BinNodePosi(T) x, VST& visit) { 
   if (!x) return;
   visit(x->data);
   travPre_R(x->lChild, visit);
   travPre_R(x->rChild, visit);
}


template <typename T> template <typename VST> 
void BinNode<T>::travIn(VST& visit) { 
   switch (rand() % 5) { 
      case 1: travIn_I1(this, visit); break; 
      case 2: travIn_I2(this, visit); break; 
      case 3: travIn_I3(this, visit); break; 
      case 4: travIn_I4(this, visit); break; 
      default: travIn_R(this, visit); break; 
   }
}


template <typename T> 
static void goAlongLeftBranch(BinNodePosi(T) x, stack<BinNodePosi(T)>& S) {
   while (x) { S.push(x); x = x->lChild; } 
}

template <typename T, typename VST> 
void travIn_I1(BinNodePosi(T) x, VST& visit) { 
   stack<BinNodePosi(T)> S; 
   while (true) {
      goAlongLeftBranch(x, S); 
      if (S.empty()) break; 
	  x = S.top();
      S.pop(); visit(x->data); 
      x = x->rChild; 
   }
}

template <typename T, typename VST> 
void travIn_I2(BinNodePosi(T) x, VST& visit) { 
   stack<BinNodePosi(T)> S; 
   while (true)
      if (x) {
         S.push(x); 
         x = x->lChild; 
      } else if (!S.empty()) {
         x = S.top();
		 S.pop();
         visit(x->data); 
         x = x->rChild; 
      } else
         break; 
}

template <typename T, typename VST> 
void travIn_I3(BinNodePosi(T) x, VST& visit) { 
   bool backtrack = false; 
   while (true)
      if (!backtrack && HasLChild(*x)) 
         x = x->lChild; 
      else { 
         visit(x->data); 
         if (HasRChild(*x)) { 
            x = x->rChild; 
            backtrack = false; 
         } else { 
            if (!(x = x->succ())) break; 
            backtrack = true; 
         }
      }
}

template <typename T, typename VST> 
void travIn_I4(BinNodePosi(T) x, VST& visit) { 
   while (true)
      if (HasLChild(*x)) 
         x = x->lChild; 
      else { 
         visit(x->data); 
         while (!HasRChild(*x)) 
            if (!(x = x->succ())) return; 
            else visit(x->data); 
         x = x->rChild; 
      }
}

template <typename T, typename VST> 
void travIn_R(BinNodePosi(T) x, VST& visit) { 
   if (!x) return;
   travIn_R(x->lChild, visit);
   visit(x->data);
   travIn_R(x->rChild, visit);
}

template <typename T> template <typename VST> 
void BinNode<T>::travPost(VST& visit) { 
   switch (rand() % 2) { 
      case 1: travPost_I(this, visit); break; 
      default: travPost_R(this, visit); break; 
   }
}

template <typename T> 
static void gotoHLVFL(stack<BinNodePosi(T)>& S) { 
   while (BinNodePosi(T) x = S.top()) 
      if (HasLChild(*x)) { 
         if (HasRChild(*x)) S.push(x->rChild); 
         S.push(x->lChild); 
      } else 
         S.push(x->rChild); 
   S.pop(); 
}

template <typename T, typename VST>
void travPost_I(BinNodePosi(T) x, VST& visit) { 
   stack<BinNodePosi(T)> S; 
   if (x) S.push(x); 
   while (!S.empty()) {
      if (S.top() != x->parent) 
         gotoHLVFL(S); 
	  x = S.top();
      S.pop(); visit(x->data); 
   }
}

template <typename T, typename VST> 
void travPost_R(BinNodePosi(T) x, VST& visit) { 
   if (!x) return;
   travPost_R(x->lChild, visit);
   travPost_R(x->rChild, visit);
   visit(x->data);
}

template <typename T> BinNodePosi(T) BinNode<T>::zig() { 
   BinNodePosi(T) lc = lChild;
   lc->parent = this->parent;
   if (lc->parent)
      ( (this == lc->parent->rChild) ? lc->parent->rChild : lc->parent->lChild ) = lc;
   lChild = lc->rChild; if (lChild) lChild->parent = this;
   lc->rChild = this; this->parent = lc;
   return lc;
}


template <typename T> BinNodePosi(T) BinNode<T>::zag() { 
   BinNodePosi(T) rc = rChild;
   rc->parent = this->parent;
   if (rc->parent)
      ( (this == rc->parent->lChild) ? rc->parent->lChild : rc->parent->rChild ) = rc;
   rChild = rc->lChild; if (rChild) rChild->parent = this;
   rc->lChild = this; this->parent = rc;
   return rc;
}

template <typename VST> struct Increase 
{
	 virtual void operator()(VST & e) {
		  cout<<e<<endl; } }; 
